1. Technical Field
The present invention relates generally to computer operating systems, and more specifically, to operating system calls in a symmetric multiprocessing (SMP) environment.
2. Related Art
Generally, computer systems are designed to accept and execute various application programs provided by a User, using an operating system to manage the computer resources required to execute the application programs.
Computer systems, and multiprocessor computer systems in particular, may manage execution of application programs by grouping program steps into “threads.” Multiprocessor systems may assign different threads from the same application program to be executed on different processors to optimise use of the available resources. Groups of program steps are more easily managed as threads rather than single program steps which would create very large management overheads.
In addition to the optimal groupings of program steps, these threads contain parameter values that ensure the threads are executed within the proper time, are properly synchronized with other threads, or satisfy other constraints of the system. Real time operating systems, for example, will force threads to be executed before certain time deadlines so that real time interaction is maintained.
Symmetric multiprocessing (SMP) is the processing of application programs and operating systems using multiple processors that share a common operating system and memory. A single copy of the operating system is available to all the processors who share equal access to a common memory via a communication path of some form. SMP systems may also be described as “tightly coupled” multiprocessing or “shared everything” systems.
The goal of an SMP system is to dynamically balance the workload between the available processors, optimising the use of the resources and providing the User with faster operation. Adding more processors to an SMP system results in faster operation, though completely linear improvement is not attainable because there are always critical sections of the Operation System that can only be executed one at a time. With completely linear improvement, two processors would run twice as fast as a single processor and three processors would run three times as fast as a single processor.
Because only a single copy of the operating system is available to all of the processors, two or more threads may attempt to access the same area of the operating system at the same time. Certain critical areas of the operating system will only be able to handle access by a single thread, otherwise causing unexpected or erroneous data to result. To prevent this, “locks” are commonly used to limit access to these critical areas to one processor or thread at a time. In order to access a critical area of the operating system, the thread must obtain the necessary lock or locks, and once it has completed execution, may make these locks available to other threads.
There are two common strategies to lock management: use of a single or global lock which locks the entire operating system, and use of multiple small locks which divide the operating system into isolated sections and lock each section separately.
In general, implementation of a single lock results in the timing shown in FIG. 1. If all three Processors 1, 2 and 3 require access to the operating system at the same time, only one will be given access and the other two must remain idle. Clearly, this strategy results in the overall system operating no faster than the speed of a single processor while operating system calls are being made. Because individual processors may operate uninhibited when they are not making operating systems calls, this strategy is still faster than a single processor.
More than one processor can access the operating system if different critical areas of the operating system are identified and a separate lock provided for each of these areas. Referring to FIG. 2, an example of the timing of this second strategy is presented. In this example, all three Processors 1, 2 and 3 require access to the operating system at the same time, but Processors 1 and 2 require access to area A of the operating system, while Processor 3 requires access to area B. Therefore, Processor 3 is free to execute its call to the operating system independent of Processors 1 and 2, which must access the operating system at different times because there is only a single lock available for each operating system area. The Microsoft NT operating system is an example of an operating system applying such a multiple lock strategy.
This multiple lock strategy suffers from a number of performance problems. As the number of locks increases, the code complexity of the lock management software and number of locks to be acquired by a given thread increases. For example, a single thread may require access to several areas of the operating system, requiring it to wait for all of the necessary locks to be made available. A thread may have obtained some, but not all of the locks it requires. While it is blocked, awaiting other locks to free up, it will be blocking any other threads waiting for the locks it has already obtained. This situation can result in deadlocking, where the computer system freezes because two threads are holding and waiting for each other's locks. Even without deadlocking, this multiple lock strategy causes more time to be spent in searching and acquiring locks, and increases the difficulty of ensuring reliability.
There is also a commercial advantage to providing an operating system that is straightforward, as it is easier for driver programmers to write programs for the operating system. Use of multiple locks increases the complexity of the operating system, making the writing of driver programs more complex and time consuming, and the operation less predictable.
The most common architecture of SMP Operating Systems is described as a monolithic operating system. Monolithic operating systems incorporate most of the functionality of the operating system into a single program file, including input and output routines. Microsoft Windows CE is an example of such a monolithic operation system.
Because of the large size of monolithic operating systems, operating system calls typically take a long period of time to execute. Therefore a single lock strategy will generally result in unacceptably long time delays to the SMP system. Because of these long delays, a multiple lock strategy is preferred over the single lock for a monolithic operating system, but suffers from the same performance problems and deadlocking hazards outlined above.
SMP systems are commonly used in personal computer and networked computer systems, high-capacity telecom switches, image processing, and aircraft simulators. As well, SMP allows customers to extend the life and increase the cost-effectiveness of their multiprocessor systems by adding processor cards and their computing power to their multiprocessors rather than buying more systems.
There is therefore a need for a method and system of Symmetric Multiprocessing that addresses the problems outlined above. This design must be provided with consideration for speed of execution, reliability, complexity and scalability.